# -*- coding: utf-8 -*-

"""剑指 Offer II 024. 反转链表
给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000"""


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """递归是不可能递归的，能用循环解决的时候，就不用递归，时间复杂度一样，递归还存在栈溢出，空间消耗累积的问题"""
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return head

        reversed, follow = None, head.next
        while head:
            head.next = reversed
            reversed = head
            head = follow
            if head:
                follow = head.next
        return reversed


if __name__ == '__main__':
    so = Solution()

    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    reversed = so.reverseList(head)
    while reversed:
        print(reversed.val, end=',')
        reversed = reversed.next
    print()


